The process of allocating and scheduling resources in order to execute certain tasks has been, and is, applied to many areas of technology. These include the use of computational resources to process data; the use of equipment and manpower resources to perform various installation and repair tasks; the use of track and signaling resources to carry trains; and the use of frequency bands or channels to carry data communications; among many others. The resources in each of these applications can be conveniently defined in terms of respective capabilities and capacities: for example, in the case of computational resources, memory and disk space are storage capabilities having a capacity defined by amounts of storage, and a microprocessor constitutes a processing capability having a capacity defined by its associated processing speed; in the case of equipment and manpower resources, equipment is a facilitating capability having a capacity defined by respective functional attributes, and manpower constitutes a skill-based capability having a capacity defined by periods of availability; in the case of track and signaling resources, track apparatus constitute a conveying capability from location A to location B and having a capacity defined by a number of trains that can be supported at any point in time, and signaling apparatus constitute a facilitating capability having a capacity defined by functional attributes; in the case of frequency bands or channels, frequency channels constitute a capability, and bandwidth of a given channel constitutes capacity of the channel.
Broadly speaking, resource scheduling involves identifying one or more resources that are capable of performing, and are available to perform, a task, or set(s) of tasks. Such tasks are defined by attributes such as start time, capacity (in terms of, among other things, duration), and capability requirements, and when faced with the problem of trying to schedule resources to perform the tasks, the attributes and availability of various resources are reviewed against those of the tasks.
In this specification, a resource is an entity having an amount of capacity that can be allocated to one or more tasks over time. The term “resource” is used herein to refer to a unit-capacity-resource, which is a type of resource that can be allocated to only one task at a time (e.g. a register in a single processor); to a batch-capacity-resource, which can simultaneously provide capacity to multiple tasks, if these tasks are synchronised to occur over the same time interval (e.g. parallel tracks of a trainline, each of which can carry one or more trains over a given distance; multiple lanes on a motorway, each of which can carry one or more cars over a given stretch of road); and to a static-aggregate-resource, which represents the composition of unit-capacity resources, members of which can be individually allocated to tasks, and where the unavailability of a member may result in unavailability of the entire resource (e.g. a delivery van without a driver (the composite resource being van and driver)). In cases where the type and/or capability of a member affects specific aspects of the allocation or scheduling process, in particular whether the unavailability of the member results in unavailability of the entire resource, it will be specified.
In certain domains, tasks frequently require use of two or more capabilities (e.g. skills) and a specified amount of the capability (i.e. capacity) either simultaneously or sequentially within a specified time period. In some cases this requirement can be met by an individual resource, such as a static-aggregate-resource, which has multiple capabilities, each of which can potentially be used either simultaneously or sequentially, and certain unit-capacity resources, which have more than one capability (with the caveat that only one capability can be used at a given time). However, a situation can arise in which existing resources are neither capable nor available for allocation to a particular task, and/or there might be a constraint mandating against use of otherwise an available and capable resource (e.g. excessive set up activities and costs associated therewith). In such situations the task cannot be scheduled, causing an existing schedule to be significantly modified (e.g. to change previously made allocations) or causing the scheduling process to fail in respect of the task. This problem can be particularly acute in a dynamic environment, where changes to tasks occur as a matter of course. Moreover, for problems having a set of interrelated tasks requiring one or more capabilities, changes to individual tasks within the set can affect other tasks in the set, introducing an additional degree of complexity to the scheduling process.
In relation to the process of scheduling itself, some known scheduling methods operate so as to split tasks requiring a plurality of capabilities into a corresponding number of individual tasks, each being linked to a or some different one(s) of the number, and each requiring a unit capacity resource. Each of the tasks is then treated by the scheduling process as an independent task (albeit having this linked inter-task dependency to other of the individual tasks). With this approach, modifications are made to the task specification and are made during process planning (or project decomposition) only, limiting the potential range of scheduling solutions that can be generated during scheduling.
In addition to issues associated with construction of a problem specification and configuring resources, developing a method for identifying potential solutions to the problem is difficult, since this involves selecting and arranging resources within the context of relational constraints between resources. Such problems have, in general, been solved by mathematical modeling techniques such as Integer Programming, which generate a problem model in which the constraints of the problem specification are expressed by means of linear relations between numerical values. For anything but basic problems, it is common to build such a model, only to find the cost of solving it prohibitive. This is because the computation effort required to solve the problem is directly related to the number of decision variables associated with the problem being modeled: for example, if a model has n 0-1 variables this would indicate 2n possible settings for the variables and 2n+1−1 potential solutions to be evaluated; it will be appreciated that, even for a small value of variables n, such as 100, 2n is very large, e.g. 2100. To address this problem, practitioners typically reformulate problems to render an easier to solve model and solution strategy. The branch and bound method rules out large sections of the potential tree from examination as being infeasible or worse than solutions already known, while other techniques reduce the number of variables to be searched by combining values, and such techniques are sophisticated, requiring dedicated algorithms and (and expensive) software packages for efficient implementation.
An alternative approach to the mathematical methods described above is to treat the scheduling problem as a constraint satisfaction problem. Such an approach is itself non-trivial, since formally representing attributes associated with resources as constraints requires a considerable amount of skill, as does developing a method of propagating the constraints.